// m

// 给定一个字符串数组chars，使用如下算法压缩
// 从空字符串s开始，对于chars中每个连续重复字符，1，如果这一组长度为1，则将字符追加到s中，2，如果这一组长度超过1，需要向s追加字符，然后跟这一组的长度
// 如果数组长度为 >= 10,则在chars数组中会被拆分为多个字符

// 设计一个使用常量额外空间的算法来解决此问题

function compress(chars) {
    function reverse(left, right) {
        while (left < right) {
            [chars[left], chars[right]] = [chars[right], chars[left]];
            left += 1
            right -= 1
        }
    }
    // 指向压缩后的当前字符串位置
    let slow = 0
    // 指向压缩前的当前字符串位置
    let fast = 0
    while (fast < chars.length) {
        // 当前带压缩字符串的起始位置 
        let fast_start = fast
        while ((fast + 1) < chars.length && chars[fast+1] === chars[fast]) {
            fast += 1 
        }

        // 将待压缩字符的起始位置的字符存入压缩后的当前字符位置，并向右移动压缩后的当前字符位置
        chars[slow] = chars[fast_start]
        slow += 1

        // 字符数目大于1将对应数量存入压缩后的当前字符位置
        if (fast - fast_start > 0) {
            let cnt = fast - fast_start + 1
            let slow_start = slow
            while (cnt !== 0) {
                chars[slow] = String(cnt % 10)
                slow += 1
                cnt = Math.floor(cnt / 10)
            }
            reverse(slow_start, slow - 1)
        }
        fast += 1
    }
    return slow
}

// let chars = ["a", "a", "b", "b",  "b", "b", "b", "b",  "b", "b", "b", "b",  "b", "b", "c", "c", "c"]
let chars = ["a", "a", "b", "b",  "b", "b", "b", "b",  "b", "b", "b", "b",  "b", "b", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c", "c",]
console.log(compress(chars));
console.log(chars)

